package com.lhcai.nk.medium;

/**
 * @author lhcstart
 * @create 2023-02-20 15:31
 */


import java.util.Scanner;

/**
 * 描述
 * 给定两个只包含小写字母的字符串，计算两个字符串的最大公共子串的长度。
 * <p>
 * 注：子串的定义指一个字符串删掉其部分前缀和后缀（也可以不删）后形成的字符串。
 * 数据范围：字符串长度： 1≤s≤150
 * 进阶：时间复杂度： O(n^3) ，空间复杂度：O(n)
 * 输入描述：
 * 输入两个只包含小写字母的字符串
 * 输出描述：
 * 输出一个整数，代表最大公共子串的长度
 */
public class HJ75 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        while (sc.hasNext()) {
            String s1 = sc.next();
            String s2 = sc.next();

            System.out.println(solution(s1, s2));

        }
    }

    public static int solution(String s1, String s2) {
        String stStr = s1.length() > s2.length() ? s2 : s1;
        String lgStr = s1.length() > s2.length() ? s1 : s2;

        int m = stStr.length();
        int n = lgStr.length();

        int[][] dp = new int[m + 1][n + 1];
        //初始化数组
        dp[0][0] = 0;
        //长字符串为空 ，最大公共子串的长度为0
        for (int i = 1; i <= m; i++) {
            dp[i][0] = 0;
        }
        //短字符串为空 ，最大公共子串的长度为0
        for (int i = 1; i <= n; i++) {
            dp[0][n] = 0;
        }

        int maxlen = 0;
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                if (stStr.charAt(i - 1) == lgStr.charAt(j - 1)) {
                    dp[i][j] = dp[i - 1][j - 1] +1;
                }

                if (dp[i][j] > maxlen) {
                    maxlen = dp[i][j];
                }

            }
        }


        return maxlen;
    }
}
